package org.chengn.level_hard.context1671;

/**
 * @Title: md
 * @Author ChengN
 * @Package org.chengn.level_hard.context1671.Context1671
 * @Date 2023/12/22 0:47
 * @description: 得到山形数组的最少删除次数
 */
public class Context1671 {
    public int minimumMountainRemovals(int[] nums) {
        int[] dpLeft = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            int maxVal = 0;
            for (int j = i - 1; j >= 0; --j) {
                if (nums[j] < nums[i])
                    maxVal = Math.max(maxVal, dpLeft[j]);

            }
            dpLeft[i] = maxVal + 1;
        }


        int[] dpRight = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; --i) {
            int maxVal = 0;
            for (int j = i + 1; j < nums.length; ++j) {
                if (nums[j] < nums[i])
                    maxVal = Math.max(maxVal, dpRight[j]);
            }
            dpRight[i] = maxVal + 1;
        }


        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; ++i) {
            if (dpLeft[i] == 1 || dpRight[i] == 1) continue;
            res = Math.min(res, nums.length - (dpLeft[i] + dpRight[i] - 1));
        }
        return res;
    }
}
